\rsec{Grafo da Web}
\label{sec:webgraph}

\begin{center}
\includegraphics[scale=0.4]{the_internet.png}\\
\scriptsize{Figura 2.1: Representação dos \textit{links} da web.}\\
\scriptsize{Fonte: \url{www.opte.org/maps}}
\end{center}

A figura anterior, apesar de não representar o verdadeiro tamanho da internet,
nos dá uma ideia de como ela se ``organiza'' e, portanto, seria interessante se
pudéssemos modelar essa estrutura amorfa em algo que faça sentido do ponto de
vista algorítmico.

Felizmente, estrutura de \textit{hyperlinks} da internet forma um grafo
dirigido. Os nós do grafo representam as páginas e as arestas dirigidas
representam os \textit{links}. Podemos representar um grafo por meio de uma
matriz de adjacência, o que seria conveniente para este trabalho, pois mais
adiante serão apresentados alguns cálculos que se utilizam de tal modelagem.
Seja $P_i$ uma página da web indexada com o inteiro $i$, então tomemos a matriz
$L$ como representação de um conjunto de páginas e seus \textit{links}:

$$
L_{ij} = \begin{cases} 
            1, & \mbox{se existe um \textit{link} de }P_i\mbox{ a }P_j\\
            0, & \mbox{caso contrário}
          \end{cases} 
$$

Mais adiante veremos que esta abstração da internet nos permite aplicar os
métodos de classificação, como o \textit{PageRank} e o HITS.

Para ilustrar, daremos um exemplo ao longo do texto que servirá para melhor
compreensão do \textit{PageRank}. Levemos em consideração o seguinte grafo como
sendo um pequeno grupo de páginas com seus \textit{links}:

\begin{center}
\includegraphics[scale=0.4]{grafo_exemplo.png}\\
\scriptsize{Figura 2.2: Grafo direcionado representando uma web de seis
páginas.}
\end{center}

Cuja matriz de adjacência é:

$$
L = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0\\
                    0 & 0 & 0 & 0 & 0 & 0\\
                    1 & 1 & 0 & 0 & 1 & 0\\
                    0 & 0 & 0 & 0 & 1 & 1\\
                    0 & 0 & 0 & 1 & 0 & 1\\
                    0 & 0 & 0 & 1 & 0 & 0\end{pmatrix}
$$


